/**
 * 
 */
package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * @ClassName   : Leetcode090 
 * @author      : ganwei 
 * @date        : 2020年5月8日
 * @Description : Leetcode090 子集 II
 */
public class Leetcode0090 {
	List<List<Integer>> result = new ArrayList<>();
	int n,k;
    /**
     * -解题思路，回溯大法
     */
	
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		Arrays.sort(nums);
		for(k = 1; k <= nums.length; k++){
			backtrack(nums,new ArrayList<Integer>(),0);
		}
    	return result;
    }
    
	/**
	 * -回溯主题
	 */
	public void backtrack(int[] nums,List<Integer> li,int index){
    	if(li.size() == k){
    		result.add(new ArrayList<Integer>(li));
    		return;
    	}
    	for(int i = index; i < nums.length; i++){
    		if(i > index && nums[i] == nums[i-1]){
    			continue;
    		}
    		li.add(nums[i]);
    		backtrack(nums,li,i+1);
    		li.remove(li.size()-1);
    	}
    	
    	
	}
	
    public static void main(String[] args){
    	int[] nums = {1,2,2};
    	Leetcode0090 l090 = new Leetcode0090();
    	l090.subsetsWithDup(nums);
    	for(List<Integer> l : l090.result){
    		for(Integer i : l){
    			System.out.print(i);
    		}
    		System.out.println();
    	}
    }
}
